Cryptographic systems—such as those of the Public-Key Infrastructure (PKI)—often involve raising elements of some group to large powers. Examples of groups include the symmetries of a geometrical object, the integers modulo a positive integer N under addition (Z/NZ), and elliptic curves. The task of raising elements of some group to (possibly) large powers is called “exponentiation”. Exponentiation is a central and expensive part of many cryptographic protocols.
Mathematically, exponentiation may be described as thus:                Let G be a group with multiplicative operator {circle around (×)}.        Given g ε G and an integer n, compute gn.The meaning of gn may be found in abstract algebra books. When n>0, it denotes the product g{circle around (×)}g{circle around (×)}g{circle around (×)} . . . {circle around (×)}g, with n copies of g being multiplied together (thus n−1 applications of ({circle around (×)}). The definition of group requires {circle around (×)} to be associative. This exponentiation obeys the algebraic laws gm{circle around (×)}gn=gm+n and (gm)n=gmn for arbitrary integers m and n. Within an abelian (=commutative) group or subgroup (the case of interest herein) exponentiation also satisfies (g{circle around (×)}h)n=gn{circle around (×)}hn.        
Three common exponentiation scenarios:                g is fixed and n varies (e.g., first phase of Diffie-Hellman);        g varies and n is fixed (e.g., RSA);        both g and n vary (e.g., second phase of Diffie-Hellman).        
Generally, the security of a cryptographic system is based, at least in part, on exponentiation being difficult to invert. That means that it is extraordinarily difficult to determine the original operands based upon the results of such exponentiation. The discrete logarithm problem tries to find n given g and gn. The Diffie-Hellman protocol uses groups in which this problem is believed to be hard. Other protocols may employ groups of unknown order (=number of elements), in which case it may be hard to find g given n and gn.
The following references discuss various exponentiation techniques (particularly those in relation to cryptography):                Donald E. Knuth, “The Art of Computer Programming”, Volume 2, Seminumerical Algorithms, 3rd edition, Addison-Wesley, 1997.        IEEE Standard Specifications for Public-Key Cryptography, IEEE Std 1363-2000, IEEE Computer Society, 29 Aug. 2000.        
Some Mathematical Notation Used HereinBjContents of bucket j, typically the product of several itemsrelated to the subscript j.CwFor fixed w, a fixed subset of Z[τ] containing small-normrepresentatives of certain residue classes modulo τw.ceil(x)Ceiling function: the least integer n such that n ≧ x, wherex is real.EAn elliptic curve equation.Ea,bThe elliptic curve y2 + xy = x3 + ax2 + bover a field of characteristic 2.floor(x)Floor function: the largest integer n such that n ≦ x, wherex is real.GF(q)Field with q elements, where q is a prime or prime power.IIdentity function (I(P) = P for all P), on elliptic curve group.log2(x)Real base 2 logarithm of x, where x is real, x > 0.mAn integer. Used for extension degree in GF(2m).μ(−1)a+1where a is taken from elliptic curve equation (EK).nAn integer, usually an exponent.pA prime.PPoint on an elliptic curve.QField of rational numbers.Q(τ)Field generated by τ. Contains all a + bτ where a, b ε Q.TfrobFrobenius endomorphism: Tfrob ((x, y)) = (xp, yp).TAn endomorphism on Koblitz curves, satisfying T2 − T + 2I = 0.Same as μTfrob.τAn algebraic integer, specifically one satisfying τ2 − τ + 2 = 0.ZRing of integers.Z[τ]Ring of integers generated by τ. Contains all a + bτ wherea, b ε Z.0Identity element (point at infinity) in an elliptic curve group.+, −, ±Addition and subtraction operators in elliptic curve group. Multiplication operator in abstract group.Fast Exponentiation
Often, the speed of an exponentiation determines its practicality. Various factors affect the speed and efficiency of exponentiation. Such factors include: which group or other algebraic system is being used, the hardware the system is implemented on, and whether one element is repeatedly being raised to different powers, different elements are raised to a fixed power, or both the powers and the base elements vary.
Binary Techniques of Exponentiation
Many of the binary techniques of exponentiation are well-known to those of ordinary skill in the art. They are explained in references (cited above).
Let x be an element of a multiplicative group (or a semigroup) with operator {circle around (×)} and let n be a positive integer. The problem is to compute xn while minimizing the number of multiplications. Herein, squarings (in which one knowingly multiplies an element by itself) are distinguished from other multiplications. For the sake of clarity and simplicity, the description, herein, assumes the time per multiplication (or squaring) is independent of the values being multiplied (or squared).
A naive technique successively computes x2=x{circle around (×)}x, x3=x2{circle around (×)}x, x4=x3{circle around (×)}x, . . . , xn=xn−1{circle around (×)}x. This takes n−1 group multiplications. It is acceptable for small n (e.g., n<20) but totally impractical when the exponent has 100 or more bits, as may happen in cryptographic applications.
Fortunately, one may lower the operation count from O(n) to O(log2(n)) using associativity. For example, one may skip the computation of x3 and proceed directly to x4=x2{circle around (×)}x2. The square-and-multiply technique, also called the left-to-right binary technique, uses at most floor(log2(n)) squarings and floor(log2(n)) additional multiplications. One may implement it by scanning the binary representation of n.
For example, if
                    n        =        1234567                                =                  1048576          +          131072          +          32768          +          16384          +          4096          +          1024          +          512          +          128          +          4          +          2          +          1                                                  =                                    (              100101101011010000111              ⁢                                                          )                        2                          ,            then the square-and-multiply technique successively computes xk for k=                2,        4,        8, 9,        18,        36, 37,        74, 75,        150,        300, 301,        602,        1204, 1205,        2410, 2411,        4822,        9644, 9645,        19290,        38580,        77160,        154320,        308640, 308641,        617282, 617283,        1234566, 1234567.        
Each bit in the binary expansion of 1234567 (excluding the leading 1) corresponds to one line above. The lines corresponding to a 1-bit represent a squaring and a multiplication. The lines corresponding to a 0-bit represent only a squaring. The algorithm uses 20 squarings and 10 additional multiplications, far fewer than the 1234566 multiplications needed by the naive technique. The square-and-multiply technique needs only one temporary, to hold the latest power of x.
The last table becomes an addition chain if one prepends a one (“1”) up front. An addition chain for n is a sequence of integers, starting with 1 and ending with n, such that every element after the 1 is the sum of two (not necessarily distinct) earlier elements. An addition-subtraction chain for n is similar but allows subtractions: each element after the 1 is the sum or difference of two earlier elements.
Another binary technique of exponentiation forms the powers x, x2, x4, x8, . . . , x1048576, where the exponents are powers of 2. Use the binary representation of n to select which subset of these to multiply together to get xn. In this casex1234567=x{circle around (×)}x2{circle around (×)}x4{circle around (×)}x128{circle around (×)}x512{circle around (×)}x1024{circle around (×)}x4096{circle around (×)}x16384{circle around (×)}x32768{circle around (×)}x131072{circle around (×)}x1048576.  (*)
This technique, called the right-to-left binary technique of exponentiation, also takes 20 squarings and 10 general multiplications. Two temporaries suffice: one to hold powers x2k and one to hold the partial product.
If the right-to-left binary technique is used multiple times, with the same x but different n, then the repeated squarings need be done only once. For example, if one already knows x2k for 0≦k≦20, then 10 general multiplications suffice to get x1234567 by (*).
Windowing
A 2kary technique (also known as radix 2k) partitions the exponent into blocks of k adjacent bits. It processes these k bits by raising the prior result to the power 2k, then multiplies the intermediate result by the contribution from the k latest bits. It is also explained in several of the above-cited references including Gordon (1998) and Knuth, p. 464.
Elliptic Curves
One family of groups used for cryptosystems is elliptic curves. Their popularity is partially based upon there being no index calculus method known to solve the discrete logarithm problem in most elliptic curve groups; therefore, a smaller key length seems to be secure. However, their main computational drawback is that adding two points on an elliptic curve typically involves several expensive multiplication operations—meaning that it takes more time and resources to process it.
In some algebraic systems, such as elliptic curve groups, two independent operations may be done more cheaply than two similar operations where the output of the first operation is an operand to the second operation. That is, it may be less expensive to compute x1{circle around (×)}x2 and x3{circle around (×)}x4 together than to compute x1{circle around (×)}x2 followed by (x1{circle around (×)}x2){circle around (×)}x3. The right-to-left binary technique lets one overlap (for example) the computations of x135=x7{circle around (×)}x128 and x256=x128{circle around (×)}x128.
For the purpose of secure communications, elliptic curves may be used for implementations of the public-key infrastructure (PKI). In such a scenario, two network-connected nodes (such as a client and a server) know a common elliptic curve and a base point. The two nodes perform a “key exchange”. This may be done to accomplish a secure communications channel, for example, when deciding on a secret key to use for a “block cipher.”
Typically, in order to accomplish a key exchange between two such nodes, each node selects an apparently random and extraordinarily large power. Each node raises the (shared) base point g to its selected power. The results are exchanged and each node raises the other node's result to its own large power. Suppose one node chooses m as its large power and the other chooses n. Due to the group identity (gm)n=gmn=(gn)m, both nodes know gmn, which can serve as a common key. Although the data being exchanged (gm and gm) are exposed along the communications path, the ultimate results (gmn) are secure because only the nodes know which “large powers” (m and n) have been used.
Koblitz Curves
One special case of elliptic curves is Koblitz curves. These curves are defined over a subfield, which means the coefficients of the defining equation are in a small subfield of a large field, but the group used for the cryptosystem is the group of points over the larger field. The term Koblitz curves usually refers to curves defined over the binary field of two elements, and they are also called anomalous binary curves. These curves appear in standards documents such as FIPS186 below.
The following references discuss elliptic curves (and/or Koblitz curves) particularly with respect to exponentiation:                [FIPS186] “Recommended Elliptic Curves for Federal Government Use”, in Appendix 6 to FIPS 186-2 “Digital Signature Standard (DSS), 2000 Jan. 2000. (Search at http:/csrc.nist.gov/encryption).        [SOLINAS] Jerome A. Solinas, “Efficient Implementation of Koblitz Curves and Generalized Mersenne Arithmetic”. Presented at the 3rd Workshop on Elliptic Curve Cryptography (ECC1999), held in Waterloo, Ontario, Canada, Nov. 1–3, 1999. For slides, go to http://cacr.math.uwaterloo.ca—select conferences.The Challenge of Fast Exponentiation        
Accordingly, it is a challenge to increase the speed and efficiency cryptography for secure communications, such as that within the PKI. Furthermore, it is a challenge to maximize the speed and security of fast exponentiation while minimizing its expense. Further still, it is a challenge to employ elliptic curves with a fast exponentiation technique so that it maximizes speed and security while minimizing expense.